package arithmetic.demo1;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 题目： 动态规划_珠宝的最大价值
 *
 */
public class Demo1 {
    public int jewelleryValue(int[][] frame) {
        int n = frame.length;
        int m = frame[0].length;


        // 状态转移方程
        int[][] dp = new int[n+1][m+1];


        for(int i =1; i<= n; i++) {
            for(int j =1 ; j <= m; j++) {

                // 进行状态转移
                if(dp[i-1][j] > dp[i][j-1]) {
                    dp[i][j] = dp[i-1][j] + frame[i-1][j-1];
                } else {
                    dp[i][j] = dp[i][j-1] + frame[i-1][j-1];
                }
            }
        }

        // 返回结果
        return dp[n][m];
    }
}


/**
 * 题目： 深搜_组合总和
 */

class Solution {
    private int  sum = 0;

    private List<Integer> path ;
    private List<List<Integer>> ret;

    private int aim ;
    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        // 创建一个空间
        ret = new ArrayList<>();
        path = new ArrayList<>();

        // 先排序
        Arrays.sort(candidates);

        aim = target;
        // 开始遍历
        dfs(candidates, 0 , 0);

        // 返回结果
        return ret;
    }


    private void dfs(int[] nums, int index , int sum) {


        // 由于这个sum 每次都需要回溯
        // 所以就设置为 参数
        if(sum == aim) {
            // 添加结果
            ret.add(new ArrayList<>(path));
            return;
        }

        if(sum > aim) {
            // 进行回退
            return;
        }


        // 进行深搜
        for(int i= index ; i<nums.length; i++) {
            path.add(nums[i]);
            dfs(nums, i, sum+nums[i]);

            // 进行恢复现场
            path.remove(path.size()-1);
        }


    }



}


/**
 * 方法二： 统计每个数字出现的个数
 */


class Solution1 {
    private int sum = 0;

    private List<Integer> path;
    private List<List<Integer>> ret;

    private int aim;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {

        // 创建一个空间
        ret = new ArrayList<>();
        path = new ArrayList<>();

        // 先排序
        Arrays.sort(candidates);

        aim = target;
        // 开始遍历
        dfs(candidates,0, 0);

        // 返回结果
        return ret;
    }

    private void dfs(int[] nums, int index , int  sum ) {

        // 由于这个sum 每次都需要回溯
        // 所以就设置为 参数
        if (sum == aim) {
            // 添加结果
            ret.add(new ArrayList<>(path));
            return;
        }

        // 防止数组越界
        if (sum > aim || index >= nums.length ) {
            // 进行回退
            return;
        }

        // 枚举每个数的个数
        for(int i =0; sum + nums[index] * i <= aim ; i++) {


            // 个数不为 0 才添加
            if(i != 0) {
                path.add(nums[index]);

            }

            // 无论个数是否为 0
            // 这里都需要进行 向下深搜
            dfs(nums, index + 1, sum + nums[index] * i);


        }


        // 注意这里的恢复现场是整体的
        for(int i=1;sum + nums[index] * i <= aim; i++) {
            path.remove(path.size()-1);
        }



    }

}



class Solution2 {

    private List<String> ret;

    private StringBuilder path;

    public List<String> letterCasePermutation(String s) {

        // new 一个空间
        ret = new ArrayList<>();
        path = new StringBuilder();
        // 进行递归
        dfs(s, 0);
        return ret;
    }

    private void dfs(String str, int pos) {
        // 递归出口
        if (pos == str.length()) {
            ret.add(path.toString());
            return;
        }


        if(str.charAt(pos) >= '0' && str.charAt(pos) <= '9') {
            // 连接数字
            path.append( str.charAt(pos));
            dfs(str, pos+1);
        } else {
            // 连接小写字母
            path.append(getLower( str.charAt(pos)));
            dfs(str, pos+1);
            // 恢复现场
            path.deleteCharAt(path.length()-1);

            // 连接大写字母
            path.append(getUpper( str.charAt(pos)));
            dfs(str,pos+1);

            // 恢复现场
            path.deleteCharAt(path.length()-1);


        }
    }

    private char getLower(char ch) {
        if (ch >= 'a' && ch <= 'z') {
            return ch;
        } else {
            return (char) (ch + 32);
        }
    }

    private char getUpper(char ch) {
        if (ch >= 'a' && ch <= 'z') {
            return  (char)(ch- 32);
        } else {
            return ch ;
        }
    }

}


/**
 * 题目： 字母大小写全排列
 *
 *
 */

class Solution3 {

    private List<String> ret;

    private StringBuilder path;

    public List<String> letterCasePermutation(String s) {

        // new 一个空间
        ret = new ArrayList<>();
        path = new StringBuilder();
        // 进行递归
        dfs(s, 0);
        return ret;
    }

    private void dfs(String str, int pos) {
        // 递归出口
        if (pos == str.length()) {
            ret.add(path.toString());
            return;
        }

        // 加上没有变化的
        char ch = str.charAt(pos);
        path.append(ch);
        dfs(str, pos+1);
        // 恢复现场
        path.deleteCharAt(path.length()-1);


        // 加上变化的
        if(ch < '0' || ch > '9') {
            // 加上没有变化的
            char tmp = change(ch);
            path.append(tmp);
            dfs(str, pos+1);
            // 恢复现场
            path.deleteCharAt(path.length()-1);
        }

    }

    private char change(char ch) {
        if(ch >= 'a' && ch <= 'z') {
            return (char)(ch - 32);
        } else {
            return (char)(ch + 32);
        }
    }

}


/**
 * 题目： 深搜_解数独
 */

class Solution4 {
    boolean[][] row;
    boolean[][] col;
    boolean[][][] grid;

    public  void solveSudoku(char[][] board) {
        // 实例化对象
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.' ) {
                    int num = (board[i][j] - '0');

                    col[j][num]= row[i][num]=grid[i / 3][j / 3][num] = true;
                }
            }
        }

        // 进行深搜
        dfs(board);
    }

    public boolean dfs(char[][] board) {

        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9;j++) {
                if(board[i][j] == '.') {
                    for(int num = 1; num <= 9 ; num++) {

                        // 剪枝
                        if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num]) {
                            row[i][num] =col[j][num] =grid[i/3][j/3][num] = true;
                            board[i][j] = (char)('0' + num);

                            // 方格都填满了的 true
                            // 然后就一直返回, 不需要考虑其他情况
                            if(dfs(board) == true) {
                                return true;
                            };

                            // 恢复现场
                            row[i][num] =col[j][num] =grid[i/3][j/3][num] = false;
                            board[i][j] = '.';
                        }
                    }
                    // 当所有数字都填完, 都没有返回 true , 就返回 false
                    return false;
                }


            }
        }

        // 当所有的方格都遍历结束了， 说明都填完了。
        return true;
    }


    public static void main(String[] args) {
        Solution4 solution4 = new Solution4();
        char[][] board = {{'5','3','.','.','7','.','.','.','.'},
                {'6','.','.','1','9','5','.','.','.'},{'.','9','8','.','.','.','.','6','.'},
                {'8','.','.','.','6','.','.','.','3'},{'4','.','.','8','.','3','.','.','1'},{'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},{'.','.','.','4','1','9','.','.','5'},{'.','.','.','.','8','.','.','7','9'}};
        solution4.solveSudoku(board);

        for (char[] chars : board) {
            System.out.println(Arrays.toString(chars));

        }
    }
}

